﻿#ifndef BinarySearchTree_H
#define BinarySearchTree_H

#include <iostream>

namespace OwnCollection {
	template <class T1,class T2>
	class BinarySearchTree {

	private:

		/*
		* Стуктура узла дерева
		*/
		struct TreeNode {
			T1 key;
			T2* value;
			TreeNode *leftChild; 
			TreeNode *rightChild; 
			TreeNode(T1 k,T2* v):key(k),value(v),leftChild(NULL),rightChild(NULL){}
			
			/*
			TreeNode(T1 k,T2* v,TreeNode *l=NULL,TreeNode *r=NULL)
			{
				key=k;
				value=v;
				leftChild=l;
				rightChild=r;
				
			}
			*/

		};


		/*
		* Память для хранения элементов коллекции
		*/
		TreeNode* root;



	public:

		BinarySearchTree():root(NULL){}

		~BinarySearchTree()
		{
			delete[] root;
		}
	

		 TreeNode* getRoot() const
		 {
			 return root;
		 }

		/*
		* Опрос размера дерева
		*/

		 int treeSize(TreeNode *cr)
		 {
			 int curSize=0;
			 int* pCurSize=&curSize;
			 treeWalk(cr,pCurSize);
			 return *pCurSize;
		 }

		/*
		* Обход дерева
		* реализуется в рекурсивной форме
		*/

		void treeWalk(TreeNode *cr,int* csum)
		{
			if(cr==NULL)
			{
				return;
			}
			treeWalk(cr->leftChild,csum);
			treeWalk(cr->rightChild,csum);
			*csum=*csum+1;
		}

		/*
		* Вертикальная печать дерева
		* 
		*/

		void treePrint(TreeNode *cr,int level)
		{
			if(cr==NULL)
			{
				return;
			}
			treePrint(cr->rightChild,level+1);
			for(int i=0;i<3*level;i++)
			{
				std::cout<<"  ";
            }
				std::cout<<cr->key<<std::endl;
                treePrint(cr->leftChild,level+1);
			
		    }


		/*
		* Длина внутреннего пути дерева
		*/


	

		/*
		* Очистка дерева
		*/
		bool clearTree()
		{
			return 0;
		}


		/*
		* Проверка дерева на пустоту
		*/
		bool isEmpty()
		{
			return 0;
		}

		/*
		* Включение данных с заданным ключом
		*/
		TreeNode* insertItem(BinarySearchTree* pTree,TreeNode *cr,T1 key,T2* val,bool* ins)
		{
			if(cr == NULL)
			{
				cr = new TreeNode(key,val);
				if(pTree->root==NULL)
				{
				pTree->root=cr;
				}
                *ins=true;
				return cr;
			}
			if (key == cr->key)
			{
				*ins=false;
				return cr;
			}
			if(key < cr->key)
			{
				cr->leftChild = insertItem(pTree,cr->leftChild,key, val, ins);
			}
			else
			{
				cr->rightChild = insertItem(pTree,cr->rightChild,key, val, ins);
			}
			return cr;		
		}


		/*
		* Удаление данных с заданным ключом
		*/
		TreeNode*  removeItem(TreeNode *cr,T1 key,bool* del)
		{
			/*
			BST_Delete(t, k, deleted)
            1.	  t – корень дерева или поддерева
            2.	  k – значение удаляемого ключа
            3.	  deleted – возвращаемый признак

            4.	if t = nil 
            5.	     then deleted ← FALSE
            6.	              return t

            7.	if k < key[t]
            8.	     then left[t] ← BST_Delete(left[t], k, del)
            9.	             deleted ← del
            10.	             return t

            11.	if k > key[t]
            12.	     then  right[t] ← BST_Delete(right[t], k, del)
            13.	               deleted ← del
            14.	               return t 

            15.	deleted ← TRUE

            16.	if left[t] = nil and right[t] = nil
            17.	     then Delete_Node ( t )
            18.	              return nil
            
			19.	if left[t] = nil
            20.	     then x ← right[t]
            21.	              Delete_Node ( t )
            22.	              return x
            
			23.	if right[t] = nil
            24.	     then x ← left[t]
            25.	             Delete_Node ( t )
            26.	             return x
            27.	right[t] ← Del(right[t], t)
            28.	return t
             */

			if(cr == null)
			{
				*del=false;
				return cr;
			}

			if(key < cr->key)
			{
				cr->leftChild =  removeItem(cr->leftChild,key,del)
				return cr;
			}

			if(key > cr->key)
			{
				cr->rightChild =  removeItem(cr->rightChild,key,del)
				return cr;
			}

			if(cr->leftChild == NULL && cr->rightChild == NULL)
			{

			}

			if(cr->leftChild == NULL)
			{

			}

			if(cr->rightChild == NULL)
			{

			}

			removeItem(cr->rightChild,key,del)

           return cr;
		}



		/*class iterator {

		//установка на первый узел в дереве с минимальным ключом

		//установка на последний узел в дереве с максимальным ключом

		//проверка состояния итератора

		//доступ по чтению и записи к данным текущего узла в дереве

		//переход к следующему по значению ключа узлу в дереве

		//переход к предыдущему по значению ключа узла в дереве


		};*/

	};
}


#endif